package com.liam.algorithm;

public class InsertSort {

    static int[] list = new int[]{3, 1, 7, 5, 9, 4, 2};

    public static void main(String[] args) {
        list = insert(list);
        for (int n : list) {
            System.out.println(n);
        }
    }

    /**
     * 插入排序     n-1 次   低效率
     * 将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。
     * 按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序
     *
     * @param list
     * @return
     */
    private static int[] insert(int[] list) {
        int temp;
        for (int i = 1; i < list.length; i++) {
            for (int j = i;j > 0 ;j--){

                if(list[j] < list[j -1]){
                    temp = list[j];
                    list[j] = list[j - 1];
                    list[j-1] = temp;
                }
            }
        }
        return list;
    }

}
